#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt; // ph[]数组存放的为插入的数在堆中的下标值，
                            // hp[]数组存放的为堆中的数对应的插入的序号

void heap_swap(int a, int b) {
	swap(ph[hp[a]], ph[hp[b]]);
	swap(hp[a], hp[b]);
	swap(h[a], h[b]);
}

void down(int u) {
	int t = u, l = 2 * u, r = l + 1;
	if (l <= cnt && h[l] < h[t]) t = l;
	if (r <= cnt && h[r] < h[t]) t = r;
	if (t != u) {
		heap_swap(t, u);
		down(t);
	}
}

void up(int u) {
	while (u / 2 && h[u] < h[u / 2]) {
		heap_swap(u, u / 2);
		u >>= 1;
	}
}

int main() {
	int n = 0, m = 0;
	cin >> n;
	
	while (n -- ) {
		char op[7];
		scanf("%s", op);
		
		if (op[0] == 'I') {
			int x;
			scanf("%d", &x);
			cnt ++ , m ++ ; // cnt 为堆中的下标，m为插入的计数器
			ph[m] = cnt, hp[cnt] = m;
			h[cnt] = x;
			up(cnt);
		}
		else if (op[0] == 'P') printf("%d\n", h[1]);
		else if (op[0] == 'D' && op[1] == 'M') {
			heap_swap(1, cnt);
			cnt -- ;
			down(1);
		} 
		else if (op[0] == 'D') {
			int k;
			scanf("%d", &k);
			k = ph[k];
			heap_swap(k, cnt);
			cnt -- ;
			down(k), up(k);
		}
		else {
			int k, x;
			scanf("%d%d", &k, &x);
			k = ph[k];
			h[k] = x;
			down(k), up(k);
		}
	}
	
	return 0;
}